/**
 * \file algo-genetique.c
 * \brief les fonctions d'algo génétique
 * \author Somayya ELMATA
 * \author Theo BRASSEUR
 * \version 0.1
 * \date 25/12/2013
 *
 * Ce fichier contient les fonctions de l'algorithme Génétique.
 *
 */



#ifndef ALGOGEN
#define ALGOGEN
#include "algo-genetique.h"
#endif

/**
 * \fn Population init_population(int taille, City* city, int nbrcity, City depart)
 * \brief initialisation de la population, (ensemble de chemins aléatoires) 
 *
 * \param taille taille de la population
 * \param city la liste des villes
 * \param nbrcitynombre de ville
 * \param departla ville de depart
 * \return une population de chemins aléatoires 
 */
Population init_population(int taille, City* city, int nbrcity, City depart)
{
	Population debut_population = NULL;
	Population nouveau = NULL;
	int i = 0;
	
	srand(time(NULL));
		
	if( taille == 0)
		printf("La taille de la population a initialiser est 0.\nFin\n");
		
	else if(taille > factorielle(nbrcity-1) )
		printf("Impossible d'initialiser une population de cette taille\nFin\n");
			
	else
	{
		while( taille_pop(debut_population) != taille )
		{
			nouveau = creer_individu(rand_path(city, nbrcity, depart));
	
			if( !(existing(debut_population, nouveau)) )
				ajouter_individu(&debut_population, nouveau);
		}
	}
	
	return debut_population;
}

/**
 * \fn void evaluation(Population *p)
 * 
 * \brief calcul de la longueur de chaque chemin dans la population 
 * \param la population 
 */
void evaluation(Population p)
{
	Population courant = NULL;
	
	for(courant = p; courant != NULL; courant = courant->next)
		(courant->trajet).dst_path = compute_path(courant->trajet);
}

/**
 * \fn void selection(Population population, int quota, int choix_methode) 
 *
 * \brief selectionne un nombre "quota" d'individu parmi la population
 * \param la population
 * \param le nombre d'individu a selectionner 
 * \param la methode a utiliser
 */
Population* selection(Population *population, int quota, int choix_methode,int nbrcity) 
{
	if(*population == NULL)
		printf("Population vide: Selection impossible\n");	
	else if(choix_methode == ELIT)                //methode elitiste
		population=elitiste(population, quota);
	else 
		population=tournoi(population, quota);			//methode tournoi
	return population;
}

/**
 * \fn void tournoi(Population population, int quota) 
 *
 * \brief la selection par methode tournoi
 * \param la population des individus
 * \param le nombre des individus à laisser
 */
Population* tournoi(Population *population, int quota) 
{
	Population courant = NULL;
	int a=0,b=0,taille=0,i;
	Population p1,p2;
	
	while ( (taille=taille_pop(*population))> quota )
	{
		//choi de deux individu au hasard
		courant=*population;
		a = rand() % taille;
		for(i = 0; i<a;i++ )
			{courant = courant->next;}
		p1=courant;
		courant=*population;
		do{
			b = rand() % taille;
		}while(a==b);
		for(i = 0; i<b;i++ )
			{courant = courant->next;}
		p2=courant;
		if((p1->trajet).dst_path >= (p2->trajet).dst_path) 
			{population=supprimer_individu(population, a);}
		else 
			{population=supprimer_individu(population, b);}

	}
	return population;
}

/**
 * \fn void elitiste(Population population, int quota)
 *
 * \brief la selection par la methode tournoi
 * \param la population des individus
 * \param le nombre des individus à laisser
 */
Population* elitiste(Population *population, int quota)
{
	Population courant = *population;
	int ind,i;
	double max=0;
	
	while ( (taille_pop(*population))> quota)
	{
		i=0;
		ind=0;
		courant=*population;
		max=(courant->trajet).dst_path ;
		while(courant != NULL )
		{	
			if((courant->trajet).dst_path > max)
			{
				max=(courant->trajet).dst_path ;
				ind=i;
				
			}	 
			courant = courant->next;
			i++;
		}
		population=supprimer_individu(population,ind);
	}
	
	return population;
}

/**
 * \fn void croisement(Population population, float proba)
 *
 * \brief opere l'hybridation
 * \param la population, la probabilite d'hybridation, le nombre de point de croisement 
 * \return la population 
 */
void croisement(Population population, float proba)
{
	int *tab = (int*)malloc(sizeof(int) *2);
	int p2=-1,i=0;
	int aleatoire = 0 ,ind=0;
	Population courant1 = population;
	Population courant2 = population;
	tab[0]=-1;tab[1]=-1;
	
	if(proba <= 0 ) return;
	
	for( courant1 = population; courant1->next != NULL; courant1 = courant1->next)
	{ 
		aleatoire = rand() % 100;
		
		if( aleatoire <= (int) (proba * 100 ))
		{
			ind = rand() % taille_pop(population);
		
			while(ind > 1)
			{
				courant2 = courant2->next;
				ind--;
			}
			
			tab=indice_croisement(courant1->trajet,courant2->trajet);
			if(croisement_valid(courant1->trajet,courant2->trajet, tab) == 0)
			{
					croiser(courant1->trajet,courant2->trajet, tab[0],tab[1]);
			}
		}
		courant2=population;
	}
	
	evaluation(population);
	free(tab);

}

/**
 * \fn int generer_indice_hybrid(int nbr_city)
 * \brief gener un ou deux point de croisement si ils existent et si il 
 * 		  y a plusieur il prend le plus long 
 *
 * \param parent1 le premier chemin
 * \param parent2 le 2eme chemin
 * \return tableau des points de croisement. 
 */
int* indice_croisement(Path parent1, Path parent2)
{
	int *tab = (int*)malloc(sizeof(int) * 2);
	int i,j=0;
	
	for(i=0;i<2;i++)
		tab[i]=-1;
	
	for(i=1;i<parent1.longueur;i++)
	{
		if(strcmp(parent1.city[i].name,parent2.city[i].name) == 0)
		{
			tab[j]=i;
			j++;
			if(j==2)j=1;
		}
	}
	if(tab[1] == -1 && tab[0] != -1) tab[1] = parent1.longueur;
	if(tab[1] - tab[0] == 1)
	{
		tab[0] = tab[1];
		tab[1] = parent1.longueur;
		
	}
	return tab;
}

/**
 * \fn int croisement_valid(Path parent1, Path parent2,int* tab)
 * \brief indique ce le croisement trouver est valide ou non
 *
 * \param parent1 le premier chemin pere
 * \param parent2 le 2eme chemin pere
 * \return 0 si le croisement est valide -1 sinon
 */
int croisement_valid(Path parent1, Path parent2,int* tab)
{
	int i,j,trv=0;
	Path fils1,fils2;
	fils1=copier(parent1);
	fils2=copier(parent2);
	if(tab[0]==-1) return -1;
	
	for(i=tab[0];i<tab[1];i++)
		for(j=tab[0];j<tab[1];j++)
		{
			if(strcmp(parent1.city[i].name,parent2.city[j].name) == 0)
				trv++;
		}
	if(trv == (tab[1]-tab[0])) 
	{
		croiser(fils1,fils2,tab[0],tab[1]);
		
		if(   compute_path(fils1) < compute_path(parent1)
			||compute_path(fils2) < compute_path(parent1)
			||compute_path(fils1) < compute_path(parent2)
			||compute_path(fils2) < compute_path(parent2) )
		
			return 0;
	}
	
	return -1;
	

}

/**
 * \fn Population mutation(Population population, int proba)
 * \brief modifier un individu
 *
 * \param l'individu a modifier
 * \return l'individu modifié
 */
Population mutation(Population population, float proba)
{
	Population courant = NULL;
	int aleatoire = 0;
	double max=0;
	Path tmp;
	if(proba <= 0 ) return population;
	else{
		for( courant = population; courant != NULL; courant = courant->next)
		{
			aleatoire = rand() % 100;
			
			if( aleatoire <= (int) (proba * 100 ))
			{
				max=compute_path(courant->trajet);
				tmp=copier(courant->trajet);
				tmp=muter(tmp);
				if(compute_path(tmp) < max)
					courant->trajet=tmp;
			}
		}
		evaluation(population);
	}
	return population;
}

/**
 * \fn Path muter(Path individu)
 * \brief modifier un individu
 *
 * \param l'individu a modifier
 * \return l'individu modifié
 */
Path muter(Path chemin)
{
	City save;
	
	int i = 0, j = 0;
	
	i = (rand() % (chemin.longueur - 1)) + 1;
		
	do{
		j = (rand() % (chemin.longueur - 1)) + 1;
	}while(j == i);
		
	save =  chemin.city[i];
	
	chemin.city[i] = chemin.city[j];
	chemin.city[j] = save;
	chemin.dst_path = compute_path(chemin);	
	
	return chemin;
}

/**
 * \fn int crossover(Path* parent1, Path* parent2)
 * \brief croise deux individu
 *
 * \param les individu à croiser
 * \return 0 si hybridation ok -1 sinon
 */
int croiser(Path parent1, Path parent2, int point1, int point2)
{
	int i = 0;
	
	Path save;
	
	save = copier(parent1);
	
	if(parent1.city == NULL || parent2.city == NULL)
	{
		printf("Erreur fonction crossover\n");
		return -1; 
	}
	if(point1==-1) return 0;
	
	for(i = point1; i < point2; i++)
	{
		parent1.city[i] = parent2.city[i];
		parent2.city[i] = save.city[i]; 
	}
	
	return 0;
}

/**
 * \fn int crit_new_generation(Population* population, int generation)
 * \brief critere de fin de l'algo
 *
 * \param la population
 * \return 1 si une nouvelle génération doit etre lancée 0 sinon
 */
int crit_new_generation(Population population, int generation, double moyenne)
{
	if(population != NULL)
	{
		if( generation <= 0 || moins_bon(population) <= moyenne)
		{
			if(generation <= 0)
				printf("Nombre de génération impartie atteint\n");
			else 
			{
				printf("La distance de parcours du moins bon individu est inférieur à la moyenne de la population initiale \n"); 
			}
			return 0;
		}
	
		else
			return 1;
	}
	
	else
	{
		printf("Population vide impossible d'evaluer le critere de nouvelle generation\n");
		return -1;
	}
}

/**
 * \fn void ajouter_individu(Population* population, Population nouveau)
 * \brief ajoute un individu a la population
 *
 * \param un pointeur sur la population
 * \param l'individu a ajouter
 */
int ajouter_individu(Population *population, Population nouveau)
{
	Population courant = NULL;
	Population precedent = NULL;
	
	if(nouveau == NULL)
		return -1;
	
	else if(*population == NULL)
		*population = nouveau;
	
	else
	{
		courant = *population;	
		precedent = *population;
			   
		while( courant != NULL )
		{
			precedent = courant;
			courant = courant->next;
		}
		
		if(courant == *population)
		{
			nouveau->next = *population;
			*population = nouveau;
		}

		else
			precedent->next = nouveau;		
	}	
	return 0;
}

/**
 * \fn void supprimer_individu(Population* population, int i)
 * \brief supprime un individu de la population
 *
 * \param un pointeur sur le premier individu
 * \param l'indice sur l'individu a supprimer
 */
Population* supprimer_individu(Population* population, int i) 
{
	Population courant = NULL, precedent = NULL;
	
	if(taille_pop(*population)<i)
	{
		printf("\nooooooooooooooooooooooo\n");
		return population;
	}
	
	if(i == 0 && *population == NULL)                                
		printf("Aucun individu dans la population\n");
	
	else if(i == 0 && *population != NULL)
	{
		if( (*population)->next == NULL)
			{free(*population);return NULL;}
		else if( (*population)->next != NULL )
		{
			precedent = *population;
			//*population = (*population)->next;
			free(precedent);
			return &((*population)->next);
		}
	}
	else
	{	
		courant = *population;
		
		while( courant != NULL && i > 0)
		{	
			precedent = courant;
			courant = courant->next;
			i--;
		}
		
		if(precedent == NULL)
		{
			printf("Impossible de supprimer l' individu n°%d\n",i);
			return population;
		}
		else
		{ 
			precedent->next = courant->next;
			free(courant);
		}
    }
    
    return population;
}

/**
 * \fn Population creer_individu(Path chemin)
 * \brief creer un individu a partir d'un chemin
 *
 * \param le chemin 
 * \return un pointure sur l'individu
 */
Population creer_individu(Path chemin)
{
	Population nouveau = NULL;
	
	nouveau =(Population) malloc(sizeof(Individu));
	nouveau->trajet = chemin;
	nouveau->next = NULL;
	
	return nouveau;
}

/**
 * \fn Path rand_path(City* villes, int longueur, City depart)
 * \brief creer un trajet aleatoire
 *
 * \param les villes du fichier, la longueur d'un trajet
 * \return le trajet aleatoire
 */
Path rand_path(City* villes, int longueur, City depart)
{
	Path chemin;
	int aleatoire = -1, i = 0;
	int* test = NULL;
	
	test = malloc(sizeof(int) * longueur);
	
	chemin.city = malloc(sizeof(City) * longueur);
	chemin.city[0] = depart;
	
	// test pour ne pas mettre les doublons plus optimisé que faire 
	// tt le chemin et le verifier à la fin
	
	for(i = 1; i < longueur; i++)
		test[i]=0;
	
	for(i = 0; i < longueur; i++)
		if(strcmp(depart.name,villes[i].name) == 0)
			test[i]=1;
	
	aleatoire = rand() % longueur;
	for(i = 1; i < longueur; i++)
	{
		while(test[aleatoire] == 1)
			aleatoire = rand() % longueur;
		
		test[aleatoire] = 1;
		chemin.city[i]=villes[aleatoire];
	}
	
	chemin.longueur = longueur;
	chemin.dst_path = compute_path(chemin);
	
	return chemin;
} 

/**
 * \fn void print_population(Population debut_population)
 * \brief affiche tous les trajets de la population actuelle
 *
 * \param le debut de la liste chainee d individu
 */
void print_population(Population debut_population)
{
	Population courant = NULL;
	
	if(debut_population != NULL)
	{
		for(courant = debut_population; courant != NULL; courant = courant->next) 
			print_path(courant->trajet);
		
		printf("\n");
	}
	else 
		printf("La population est vide: Impossible d'afficher\n");
}

/**
 * \fn int existing(Population indiv)
 * \brief dit si un individu indiv existe deja dans la population ou pas
 *
 * \param un pointeur sur le premier individu, l'individu a supprimer
 * \return 1 si existe deja autre chose sinon
 */
int existing(Population debut_population, Population indiv)
{
	Population courant = NULL;
	
	courant = debut_population;
	
	while( courant != NULL )
	{
		if( compare_path(courant->trajet, indiv->trajet) == 0 )
			return 1;
		
		courant = courant->next;
	} 
	
	return 0;
}

/**
 * \fn int compare_path(Path a, Path b)
 * \brief compare deux trajet
 *
 * \param les deux trajets a comparer
 * \return 0 si pareil, 1 sinon
 */
int compare_path(Path a, Path b) 
{
	int i = 0, identique = 0;
	
	for(i=0;i<a.longueur;i++)
	{
		if( compare_city(a.city[i], b.city[i]) == 0 )
			identique++;	
	}
	
	if(identique == a.longueur)
		return 0;
	else 
		return 1;
}

/**
 * \fn Path copier(Path modele)
 * \brief copie un trajet en créant un nouveau trajet mirroir du modèle
 *
 * \param le trajet a copier
 * \return le trajet copier
 */
Path copier(Path modele)
{
	Path copy;
	int i = 0;
	
	copy.city = malloc(sizeof(City) * modele.longueur);
	
	for(i = 0; i < modele.longueur; i++)
	{
		copy.city[i].name = malloc(sizeof(char) * strlen(modele.city[i].name));
		strcpy(copy.city[i].name, modele.city[i].name);
		copy.city[i].x=modele.city[i].x;
		copy.city[i].y=modele.city[i].y;
	}
	
	copy.longueur = modele.longueur;
	copy.dst_path = compute_path(modele);
	
	return copy;
}

/**
 * \fn int taille_pop(Population debut_population)
 * \brief donne la taille actuelle de la population
 *
 * \param le debut de la liste chainee d'individu
 * \return la taille de la population
 */
int taille_pop(Population debut_population)
{
	Population courant = NULL;
	int taille = 0;
	
	for(courant = debut_population; courant != NULL; courant = courant->next)
		taille++;
	
	return taille;
}

/**
 * \fn long int factorielle(int n)
 * \brief calcul de factorielle 
 *
 * \param un nombre entier n
 * \return le factorielle du nombre n
 */
long int factorielle(int n)
{
	int i=0;
	long int temp=n;
	while(i<=n-2)
	{
		i=i+1;
		temp=temp*(n-i);
	}
	return temp;
}

/**
 * \fn double get_dst_chemin(Population population, int ind)
 * \brief retourn la longueur du chemain d'indice ind
 *
 * \param popullation un pointeur sur le premier individu
 * \param ind l'indice sur l'individu a chercher
 */
double get_dst_chemin(Population population, int ind)
{
	Population courant = NULL;
	courant = population;
	int i;

	for(i=0;i<ind;i++)
		courant=courant->next;
	
	return (courant->trajet).dst_path;
}

/**
 * \fn int compare_city(City a, City b)
 * \brief compare deux ville
 *
 * \param les deux villes a comparer
 * \return 0 si pareil, 1 sinon
 */
int compare_city(City c1, City c2 )
{
	if( strcmp(c1.name, c2.name) == 0 && c1.x == c2.x && c1.y == c2.y )
		return 0;
	
	return 1;
}

/**
 * \fn void free(population(Population population)
 * \brief free la population
 *
 * \param la population
 */
void free_population(Population population)
{
	Population courant = NULL, precedent = NULL;
	
	for(courant = population; courant->next != NULL; courant = courant->next)
	{
		precedent = courant;
		free(precedent);
	}	
}

/** 
* \fn double moyenne(Population population)
* \brief calcule la moyenne des distances parcourues pour tous les trajet
* \param la population 
* \return la moyenne */ 
double compute_moyenne(Population p) 
{ 
	Population courant = NULL; 
	double moyenne = 0; 
	
	if(p != NULL)
	{
		for(courant = p; courant != NULL; courant = courant->next) 
			moyenne += (courant->trajet).dst_path; 
	}
	else
	{
		printf("La population est vide impossible de calculer la moyenne\n");
		return -1;
	} 
			
	return ( moyenne / taille_pop(p) ); 
}

/** 
* \fn double moins_bon(Population population) 
* \brief retourne la distance du moins bon trajet
* \param la population
* \return la distance du moins bn trajet 
*/ 
double moins_bon(Population p) 
{ 
	Population courant = NULL; 
	double worst = 0; 
	
	if(p != NULL)
	{
		worst = (p->trajet).dst_path;
	
		for(courant = p; courant != NULL; courant = courant->next) 
		{
			if( (courant->trajet).dst_path > worst )
				worst = (courant->trajet).dst_path;
		}
	}
	else
	{
		printf("La population est vide impossible de calculer le trajet le moins bon\n");
		return -1;
	} 
					
	return worst; 
}

Path plus_court_chemin(Population p)
{
	Population courant = NULL; 
	double min ;
	int i=0,ind=0;
	
	min =(p->trajet).dst_path ;
	for(courant = p; courant != NULL; courant = courant->next) 
	{
		if( (courant->trajet).dst_path < min )
		{
			min = (courant->trajet).dst_path;
			ind=i;
		}
		i++;
	}
	courant=p;
	for(i=0;i<ind;i++)
		courant = courant->next;
	
	return (courant->trajet);
	
}
